Exercise 14 (Homework 2).
(regular languages,
minimization of DFAs,
pigeonhole principle,
hard exercise)
At least k occurrences of every symbol is a regular language
Given k\in \mathbb N, consider the language
L_k=\{w\in \{a,b,c\}^* \mid |w|_a\geq k \land |w|_b\geq k \land |w|_c\geq k\}\ .
Show that for any k, L_k is a regular language.
How many states (as a function of k) does the minimum DFA recognizing L_k have?